The growth of Internet Protocol (IP)-based networks as carriers for various types of digital communications has led to the advent of application protocols used to negotiate and define the parameters of a communications session between two peer computing devices. One example of such an application protocol is Session Initiation Protocol (SIP), commonly used for establishing and managing Voice-over-IP (VoIP) connections.
Along with the rise of IP-based networks and digital communications has come the need to protect such networks and the devices that reside on them from security vulnerabilities and attacks. To provide for secure communications, many private communication networks connect to public networks (e.g., Internet) using a network security device, such as a firewall device, a NAT device, or a computing device executing software that performs firewall, NAT, and/or other security functions. Generally, these types of network security devices mask the local addresses of client devices within the private network.
FIG. 1 is a block diagram illustrating a typical network configuration 100 for providing secure communications between private communications networks. The configuration 100 includes two client computing devices 102a and 102b, two NAT devices 104a and 104b, located within private networks 106a and 106b, respectively, which act as an interface between the client devices 102a and 102b and the network device 108. As shown in FIG. 1, client device 102a in private network 106a establishes a session (e.g., SIP session) with client device 102b by communicating with NAT device 104a, which transmits the communication via the network device 108 to NAT device 104b in private network 106b and then to client device 102b. 
For security purposes, most NAT devices prevent unsolicited inbound communications from reaching client devices that are located behind them in the network. Instead, most NAT devices allow inbound communications, such as IP packets, to reach a client device only if an existing packet flow already exists that matches the inbound packets. In general, a flow is defined with a source IP address, source port, destination IP address, destination port and protocol type (e.g., TCP). A flow is created by a packet sent from the client device (or endpoint) behind the NAT device to the network. When the initial packet sent from the client device reaches the NAT device, the NAT device creates a binding associated with the packet. The binding maps the static, private IP address of the client device to a temporary public IP address selected by the NAT device from a pool of reusable IP addresses. Because the NAT device has a finite number of reusable IP addresses, a binding created by a NAT device is also associated with a timeout value. If no packets that use the binding are received by the NAT within the timeout window, then the binding is removed from the NAT device and the temporary IP address is returned to the pool for future use.
The paradigm of requiring a client device to initiate a flow and allowing a binding to expire if not used within a certain amount of time presents certain difficulties in the context of a SIP session. For example, it is common for a network device (e.g., a VoIP server) to send a SIP INVITE request to a client device that is located behind a NAT device in order to set up a SIP session (e.g., a VoIP call). However, unless the client device had already established a flow with the network device by sending a packet to the network, the IP packet carrying the INVITE request would be intercepted by the NAT device and be prevented from reaching the client device. Therefore, a client device may register for SIP sessions by transmitting an SIP REGISTER message to the network device, which creates a binding at the NAT device to be used for SIP signaling. However, because the NAT binding is associated with a timeout value, the registration of the client device must be refreshed regularly to avoid removal of the binding.
Some commonly-used methods of refreshing the registration are:
Fast Registration Refresh                The network device may force the client device to use short refresh intervals to keep the binding open. The refresh interval must be shorter than the NAT binding timeout value.        
Simple Traversal of UDP Through NATs (STUN) Keepalives                STUN keepalive messages are sent periodically by the client device to keep the binding alive. The sending interval must be shorter than the NAT binding timeout value.        
Sending Empty Lines as SIP Messages                Carriage Return-Line Feed (CRLF) characters are sent periodically by the client device. The sending interval must be shorter than the NAT binding timeout value.        
All of the above-referenced methods for refreshing the registration require that the sending interval be shorter than the NAT binding timeout value. However, the NAT binding timeout value is generally not known by the network device prior to establishing a registration because the NAT devices are not controlled by the operator of the network device. Accordingly, the network device must force the sending interval to be less than the lowest anticipated NAT binding timeout value—resulting in the potential transmission of a large number of refresh messages in order to ensure that the bindings are kept alive. This additional traffic substantially hampers network bandwidth and performance, and also affects the power consumption and efficiency of the client devices. For example, if a sending interval is set to 30 seconds, 10% of NAT devices have a binding timeout value of 45 seconds and 90% of NAT devices a binding timeout value of 120 seconds, more than double of the messages sent to keep the bindings alive are unnecessary. Therefore, it is desirable to estimate the NAT binding timeout value as accurately as possible without the potential of underestimation.
One method of learning the NAT binding timeout value is to increase the SIP registration refresh time gradually, while also making use of SIP OPTIONS requests. This learning method operates as follows:                i) Initially the refresh interval is set to x, where x is known as being an estimate of the shortest binding lifetime used by a NAT device;        ii) Before x expires but close to its expiration time, one or more SIP OPTIONS messages are sent from the network device to the client device. If the network device receives replies to the SIP OPTIONS messages, this indicates that the binding in the NAT device is still alive and the OPTIONS messages were received by the client device. The refresh interval x is increased by y unless x+y>Max, where Max is the upper limit provisioned for the sending interval. If the network device does not receive a reply, x is decreased by z. In either case, transmission of SIP OPTIONS messages is repeated with the new value of x. The process stops if x+y>Max, or if x keeps changing within a narrow range.        iii) After the binding timeout estimation is completed, this value is used as the registration expiration value. This state is referred to as “stable state.” SIP OPTIONS messages are sent periodically close to the expiration time to determine whether the NAT binding timeout value has changed. If the network device does not receive a reply, this indicates that the NAT binding timeout value has changed and the network device restarts the process of determining the timeout value.        
However, the above learning method has certain disadvantages. This learning method starts from the lowest possible NAT binding timeout value and increases gradually in small steps. As a result, the learning method takes a long time to complete. Also, when a sending interval bigger than the NAT binding timeout value is used, there will be a period during which the NAT binding is removed but the registration refresh timer has not yet expired. In this period, SIP calls initiated from the network device will not be able to reach the client device.